package com.itheima.leetcode.od.b.backtracking;

import java.util.Arrays;
import java.util.LinkedList;

/**
 * <h3>套皮K数之和</h3>
 * (B卷,100分)- 符合要求的元组的个数（Java & JS & Python & C）
 * <p>
 * 题目描述
 * <p>
 * 给定一个整数数组 nums、一个数字k，一个整数目标值 target，请问nums中是否存在k个元素使得其相加结果为target，请输出所有符合条件且不重复的k元组的个数
 * <p>
 * 数据范围
 * <p>
 * 2 ≤ nums.length ≤ 200
 * -10^9 ≤ nums[i] ≤ 10^9
 * -10^9 ≤ target ≤ 10^9
 * 2 ≤ k ≤ 100
 * <p>
 * 输入描述
 * <p>
 * 第一行是nums取值：2 7 11 15
 * <p>
 * 第二行是k的取值：2
 * <p>
 * 第三行是target取值：9
 * <p>
 * 输出描述
 * <p>
 * 输出第一行是符合要求的元组个数：1
 * <p>
 * 补充说明：[2,7]满足，输出个数是1
 * <p>
 * 用例
 * <p>
 * 输入	-1 0 1 2 -1 -4
 * 3
 * 0
 * 输出	2
 * 说明	[-1,0,1]，[-1,-1,2]满足条件
 * 输入	2 7 11 15
 * 2
 * 9
 * 输出	1
 * 说明	[2,7]符合条件
 */
public class KSum {

    public static void main(String[] args) {
        /*Scanner sc = new Scanner(System.in);

        int[] nums = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int k = Integer.parseInt(sc.nextLine());
        int target = Integer.parseInt(sc.nextLine());*/

        int[] nums = Arrays.stream("-1 0 1 2 -1 -4".split(" "))
                .mapToInt(Integer::parseInt)
                .toArray();
        int k = Integer.parseInt("3");
        int target = Integer.parseInt("0");

        System.out.println(getResult(nums, k, target));
    }

    public static int getResult(int[] nums, int k, int target) {
        if (k > nums.length) {
            return 0;
        }
        Arrays.sort(nums); // 排序很关键，去重需要
        return kSum(nums, k, target, 0, 0, new LinkedList<>());
    }

    // k数之和
    public static int kSum(int[] nums, int k, int target, int start, int count, LinkedList<Integer> stack) {

        if (k == 2) {
            return twoSum(nums, target, start, count);
        }

        for (int i = start; i < nums.length - 2; i++) {
            // 去重 组合无重复
            if (i > start && nums[i] == nums[i - 1]) {
                continue;
            }

            stack.push(nums[i]);
            count = kSum(nums, k - 1, target - nums[i], i + 1, count, stack);
            stack.pop();
        }

        return count;
    }

    // 两数之和
    public static int twoSum(int[] nums, int target, int start, int count) {
        int l = start;
        int r = nums.length - 1;

        while (l < r) {
            long sum = nums[l] + nums[r];

            if (target < sum) {
                r--;
            } else if (target > sum) {
                l++;
            } else {
                count++;
                // 继续查找其他的解
                l++;
                r--;
                while (l < r && nums[l] == nums[l - 1]) { // 组合无重复
                    l++;
                }
                while (l < r && nums[r] == nums[r + 1]) { // 组合无重复
                    r--;
                }
            }
        }

        return count;
    }
}